//给定一个二叉树，判断其是否是一个有效的二叉搜索树。 
//
// 假设一个二叉搜索树具有如下特征： 
//
// 
// 节点的左子树只包含小于当前节点的数。 
// 节点的右子树只包含大于当前节点的数。 
// 所有左子树和右子树自身必须也是二叉搜索树。 
// 
//
// 示例 1: 
//
// 输入:
//    2
//   / \
//  1   3
//输出: true
// 
//
// 示例 2: 
//
// 输入:
//    5
//   / \
//  1   4
//     / \
//    3   6
//输出: false
//解释: 输入为: [5,1,4,null,null,3,6]。
//     根节点的值为 5 ，但是其右子节点值为 4 。
// 
// Related Topics 树 深度优先搜索 
// 👍 685 👎 0

package leetcode.editor.cn;

import common.bean.TreeNode;

/**
 * Java：验证二叉搜索树
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P98_ValidateBinarySearchTree {
    public static void main(String[] args) {
        Solution solution = new P98_ValidateBinarySearchTree().new Solution();
        // TODO 此处开始你的表演

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    /**
     * 递归
     */
    class Solution {
        public boolean isValidBST(TreeNode root) {
            return isValidBST(root, null, null);
        }

        private boolean isValidBST(TreeNode root, Integer min, Integer max) {
            if(root == null) {
                return true;
            }
            if(min != null && root.val <= min) {
                return false;
            }
            if(max != null && root.val >= max) {
                return false;
            }
            return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);

        }
    }

    //leetcode submit region end(Prohibit modification and deletion)

}
